package tree.递归;

import po.TreeNode;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName N在二叉树中分配硬币979.java
 * @Description https://leetcode-cn.com/problems/distribute-coins-in-binary-tree/
 * @createTime 2021年08月12日 19:32:00
 */
public class N在二叉树中分配硬币979 {
	int res=0;
	public int distributeCoins(TreeNode root) {
		//如果最后根节点位置的值为0，说明左右节点都存在了硬币，也就是左子树的移动的硬币个数+右子树的移动硬币的个数=总的个数
		if (dfs(root)==0){
			return res;
		}else {
			return -1;
		}
	}

	private int dfs(TreeNode root) {
		if (root == null) {
			return 0;
		}
		//左节点移动的步数的总和
		int left=dfs(root.left);
		res+=Math.abs(left);
		//右节点移动的步数的总和
		int right=dfs(root.right);
		//这里去绝对值是因为，如果节点没有硬币，那么就会为负数（从别的节点移动硬币过来）。而移动过来也算作移动的步数
		res+=Math.abs(right);
		//当前节点可以移动的金币数量
		return left+right+ root.val-1;
	}
}
